  //一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出
//这个数字。 
//
// 
//
// 示例 1: 
//
// 输入: [0,1,3]
//输出: 2
// 
//
// 示例 2: 
//
// 输入: [0,1,2,3,4,5,6,7,9]
//输出: 8 
//
// 
//
// 限制： 
//
// 1 <= 数组长度 <= 10000 
// 👍 171 👎 0

  
  package com.ainge.easystudy.leetcode.editor.cn;
  public class QueShiDeShuZiLcof{
      public static void main(String[] args) {
           Solution solution = new QueShiDeShuZiLcof().new Solution();
      }
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int missingNumber(int[] nums) {
        /**
         * a^a = 0；
         * a^0 = a;
         * a^b^c = a^c^b;
         */
        // 长度为n的有序递增数组，缺少某个值；
        // 令取一个长度为n+1数组有序，数组两两异或，最后相同的值都被消除为0，剩下的那个就是缺失的。
        int xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= (nums[i] ^ i);
        }
        // 另一个数组还漏了最末尾的没有异或
        return xor ^ nums.length;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

  }
